import java.util.Arrays;

/**
 * 738. 单调递增的数字
 * https://leetcode-cn.com/problems/monotone-increasing-digits/
 */
public class Solutions_738 {
    public static void main(String[] args) {
//        int N = 10;  // output: 9
//        int N = 1234;  // output: 1234
        int N = 332;  // output: 299
//        int N = 100;  // output: 99
//        int N = 20;  // output: 19

        int result = monotoneIncreasingDigits(N);
        System.out.println(result);
    }

    public static int monotoneIncreasingDigits(int N) {
        char[] arr = String.valueOf(N).toCharArray();

        for (int i = arr.length - 1; i > 0; i--) {
            // 当前位比前一位要小，那么前 1 位减 1，当前位及后面所有的位，都变成 9
            if (arr[i] < arr[i - 1]) {
                arr[i - 1] -= 1;
                // 不仅当前位变成 9，后面所有的位都要变成 9，因为 100 的结果是 99，而不是 90
                Arrays.fill(arr, i, arr.length, '9');
            }
        }
        // 将合法的字符串形式数字，转换成数值
        return Integer.valueOf(String.valueOf(arr));
    }
}
